package offer.offer12;

/**
 * @Author: wjy
 * @Date: 2021/10/26 16:24
 */
public class Solution {

    /**
     * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     *
     * 示例 1：
     *
     * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
     * 输出：true
     *
     * 示例 2：
     *
     * 输入：board = [["a","b"],["c","d"]], word = "abcd"
     * 输出：false
     *
     * @param args
     */
    public static void main(String[] args) {

        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','C','E','E'}};
        //char[][] board = {{'a', 'b'}};
        //char[][] board = {{'C', 'A', 'A'}, {'A', 'A', 'A'}, {'B', 'C', 'D'}};
        String word = "ABCCEC";
        //String word = "ba";
        //String word = "AAB";

        Solution solution = new Solution();
        System.out.println(solution.exist(board, word));

    }

    public boolean exist(char[][] board, String word) {

        if (word.length() == 0) {
            return false;
        }

        int index = 0;

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (this.check(i, j, board, word, index)) {
                    return true;
                }
            }
        }

        return false;

    }

    public boolean check(int x, int y, char[][] board, String word, int index) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 0 || index >= word.length()) {
            return false;
        }

        if (board[x][y] == word.charAt(index)) {
            board[x][y] = 0;
            if (this.check(x - 1, y, board, word, index + 1)) {
                return true;
            }
            if (this.check(x + 1, y, board, word, index + 1)) {
                return true;
            }
            if (this.check(x, y - 1, board, word, index + 1)) {
                return true;
            }
            if (this.check(x, y + 1, board, word, index + 1)) {
                return true;
            }

            board[x][y] = word.charAt(index);

            if (index == word.length() - 1) {
                return true;
            }

        }
        return false;

    }

}
